#include <iostream>
using namespace std;

struct ListNode
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int Arr[], int len)
	{
		this->val = Arr[0];
		this->next = NULL;
		ListNode *pp = this;
		for (int i = 1; i < len; i++)
		{
			ListNode *p = new ListNode(Arr[i]);
			pp->next = p;
			pp = p;
		}
	}

	void print()
	{
		ListNode *p = this;
		while (p != NULL)
		{
			cout << p->val << " ";
			p = p->next;
		}
	}
};

class Solution
{
  public:
	ListNode *reverseBetween(ListNode *head, int m, int n)
	{
		ListNode *p = head;
		ListNode *pre = NULL, *pret = NULL;
		int len = n - m + 1;
		int mm = m - 1;
		if (mm <= 0)
		{
			pre = NULL;
			pret = NULL;
		}
		else
		{
			while (--mm)
			{
				p = p->next;
			}
			pre = p;
			pret = p;
			p = p->next;
		}
		ListNode *cur = p, *curt = p;
		ListNode *nex = NULL;
		while (len--)
		{
			nex = cur->next;
			cur->next = pre;
			pre = cur;
			cur = nex;
		}
		pret->next = pre;
		curt->next = nex;
		return head;
	}
};

int main()
{
	int Arr[] = {1, 2, 3, 4, 5};
	int length = sizeof(Arr) / sizeof(Arr[0]);
	ListNode *list = new ListNode(Arr, length);
	list->print();
	cout << endl;
	list = Solution().reverseBetween(list, 1, 4);
	list->print();
	return 0;
}
